package service;

/**
 * Created by fanzhenyu02 on 2020/7/23.
 * count bit x in 1~n
 */
public class CountXService {


    public long startTime = System.currentTimeMillis();

    /**
     * count bit x in 1~n
     * sorry for the first brute force soulution.
     *
     * @param n
     * @param x
     * @return
     */
    int countBitX(int n, int x) {
        int count = 0, k;
        for (int i = 1; (k = n / i) > 0; i *= 10) {
            // number in high end.
            int high = k / 10;
            if (x == 0) {
                if (high > 0) {
                    high--;
                } else {
                    break;
                }
            }
            count += high * i;
            int cur = k % 10;
            if (cur > x) {
                count += i;
            } else if (cur == x) {
                // n - k * i indicates lower end number.
                count += n - k * i + 1;
            }
        }
        return count;
    }


    public static void main(String[] args) {
        CountXService an = new CountXService();
        System.out.println(an.countBitX(999, 9));

        System.out.println("\ntotal time consume: " + (System.currentTimeMillis() - an.startTime) + " ms.");
    }


}
